There are many applications that require the fast production of random numbers including a plurality of bits. Such applications include cryptographic key generation in key servers, session keys, and nonces; simulations; Monte Carlo or randomized computations; dithering; gambling; and games. Often buffered, off-line generated random numbers can be used, but this requires a large buffer and there is a significant initial delay (i.e., latency), before the buffer is filled.
Many physical (i.e., true) random number generators use low quality (drifting) oscillators, sampled at a fixed rate. Oscillators are subject to phase noise and jitter. Phase noise and jitter are both measures of timing uncertainty in the output of an oscillator. Phase noise refers to the frequency domain uncertainty of an oscillator, while jitter is a measure of oscillator uncertainty in the time domain. If the oscillator signal is sampled at a sample rate slow enough for the phase of the oscillator to be able to drift at least a full period time, the sample will be random.
The source of the phase noise and jitter can be random (e.g., noise) or deterministic (e.g., caused by external influences). Phase noise and jitter cause amplitude and phase deviations. Phase deviation accumulates in time and drifts without bound. Phase noise and jitter can be modeled as non-stationary random processes.
Random jitter comes from many sources. Such sources include: thermal noise (e.g., vibrations of semiconductor crystal structure), imperfections due to semiconductor process variation, avalanche noise, shot noise, etc.
Deterministic jitter is created by interference signals, such as crosstalk between adjacent signal traces, electromagnetic interference (EMI) radiation, alternating current (AC) power lines, radio frequency (RF) signal sources, vibrations, noise in power layers of a multi-layer substrate, load variations caused by other parts of the circuit, etc. The noise can modulate signal voltage levels, change threshold voltages in logic gates, or change the ground reference, resulting in varying the required voltage to switch the gate, and so altering the switching time point of finite slew rate signals.
The drifting oscillator can be built as a ring oscillator that includes an odd number of inverters (or other inverting gates) connected in series (i.e., a ring), with an output fed back to the first inverter. The inverters or gates can be taken from standard digital component libraries provided by chip manufacturers. However, these gates are designed to be insensitive to noise, having very little dependency from the supply voltage, and they have large analog gain, so the switching point is quite stable. To see enough drift, millions of switching events have to take place.
If an n-stage ring oscillator output is sampled at a rate such that the expected phase drift reaches a full period time of the output, the complexity of the circuit increases linearly with the number of inverters n; the power consumption increases quadratically; and the throughput (i.e., the number of random bits generated in unit time) decreases quadratically. The largest throughput is achieved using oscillators of the shortest ring possible. For stable oscillation, the product of the analog gains of the inverters must be much larger than one at the oscillation frequency. If the product of gains is close to one, the circuit produces a sinusoidal oscillator of small output signal amplitude; if the gain is less than one, the circuit settles to an intermediate DC voltage, both of which result in large power consumption.
One can slow down the gates, for example, by inserting large resistors in series to their inputs, which form integrators with the input capacitances. This results in larger noise sensitivity, and so larger phase drift. However, resistors are not part of standard digital component libraries, so some workaround is needed, like using analog switches of finite resistance. The resistance values vary and are not always thoroughly specified, making the oscillators hard to reproduce and a redesign would be necessary at each minor change of the manufacturing process.